Definišimo funkciju F(n):
F(0) = 0, F(1) = 1
F(n) = F(n−1) + F(n−2)
Poznato je da se n-ti element Fibonacijevog niza može izračunati mnogo brže od linearne rekurzije koristeći sledeće formule:
Za k ≥ 0:
F(2k) = F(k) ⋅ (2F(k+1)−F(k))
F(2k+1) = F(k+1)2 + F(k)2
Napisati rekurzivnu funkciju koja računa F(n) u
vremenskoj složenosti O(logn).
Jedan ceo broj n(0≤n≤1018).
Ispisati vrednost F(n) po modulu 109 + 7.
105550586268941